package offer.offer03;

import java.util.ArrayList;
import java.util.List;

/**
 *
 */
public class Solution38_2 {
    List<String> list = new ArrayList();

    public String[] permutation(String s) {
        //s.toCharArray()返回一个char[], 为包含s中所有char的数组
        help(s.toCharArray(),0);
        //把私有的list从集合变成数组之后返回;
        return list.toArray(new String[0]);
    }

    void help(char[] cs ,int index){
        if(index==cs.length){
            //String(char[])会把char[]中的元素拼起来
            list.add(new String(cs));
            return;
        }
        for(int i=index;i<cs.length;i++){
            if(isRepeat(cs,index,i)) continue;
            swap(cs,index,i);
            help(cs,index+1);
            swap(cs,index,i);
        }
    }

    //从cs的index到i中间, 有任何一个与cs[i]的值相同的, 就true
    boolean isRepeat(char[] cs, int index, int i){
        for(int j = index ;j<i;j++){
            if(cs[j]==cs[i]) return true;
        }
        return false;
    }

    //交换char[] cs 的i位和j位
    void swap(char[] cs, int i, int j){
        char temp = cs[i];
        cs[i] = cs[j];
        cs[j] = temp;
    }
    public static void main(String[] args) {
        String input = new String("zhoz");
        String[] output = new Solution38_2().permutation(input);
        for(String s: output){
            System.out.println(s);
        }
    }
}
